package com.xj.algorithm.leetcode;

/**
 * 两数之和--中级版
 */
public class L2_逆序的双链表模拟两数相加 {

    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     *
     * 注意事项：当一个列表为空时，即出现空列表
     */

    public static void main(String[] args) {
        ListNode l1=new ListNode(2);
        l1.next=new ListNode(4);
        l1.next.next=new ListNode(3);

        ListNode l2=new ListNode(5);
        l2.next=new ListNode(6);
        l2.next.next=new ListNode(4);

        ListNode res=addTwoNumbersOffice(l1,l2);
        while(res!=null){
            System.out.print(res.val);
            res=res.next;
            if(res!=null){
                System.out.print("->");
            }
        }
        System.out.println();
    }

    //我的解法
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result=null;
        ListNode index=null;
        int carry=0;
        while(l1!=null && l2!=null){
            int sum=l1.val+l2.val+carry;
            carry=sum/10;
            sum=sum%10;

            ListNode tmp=new ListNode(sum);
            if(result==null){
                result=tmp;
                index=tmp;
            }else {
                index.next = tmp;
                index=tmp;
            }
            l1=l1.next;
            l2=l2.next;
        }
        while(l1!=null){
            int tmpVal = l1.val+carry;
            carry=tmpVal/10;
            tmpVal=tmpVal%10;
            l1.val=tmpVal;

            index.next=l1;
            index=l1;
            l1=l1.next;
        }
        while(l2!=null){
            int tmpVal = l2.val+carry;
            carry=tmpVal/10;
            tmpVal=tmpVal%10;
            l2.val=tmpVal;

            index.next=l2;
            index=l2;
            l2=l2.next;
        }
        if(carry>0){
            index.next=new ListNode(carry);
        }
        return result;
    }

    //官方最优解：只使用了一个while。
    public static ListNode addTwoNumbersOffice(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
      val = x;
  }
}